package NC97_字符串出现次数的TopK问题_最小堆解法;

import java.util.*;

class Comp implements Comparator<Map.Entry<String, Integer>>{

    @Override
    public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
        if (o1.getValue().equals(o2.getValue())){
            // 字典小的在前 所以 o1 比 o2
            return o2.getKey().compareTo(o1.getKey());
        }else {
            // 数量小的在前 所以 o1 - o2
            return o1.getValue() - o2.getValue();
        }
    }
}

public class Solution {
    /**
     * return topK string
     * @param strings string字符串一维数组 strings
     * @param k int整型 the k
     * @return string字符串二维数组
     */
    public String[][] topKstrings (String[] strings, int k) {
        // write code here
        if (strings == null || k == 0){
            return new String[][]{};
        }
        Comp comp = new Comp();
        String[][] res = new String[k][2];
        TreeMap<String, Integer> map = new TreeMap<>();
        // 统计每次字符出现的次数
        for (String s : strings) {
            if (map.containsKey(s)) {
                map.put(s, map.get(s) + 1);
            } else {
                map.put(s, 1);
            }
        }
        PriorityQueue<Map.Entry<String, Integer>> queue = new PriorityQueue<>(k, comp);
        for (Map.Entry<String, Integer> entry : map.entrySet()){
            // 堆的元素个数小于 k，则直接加入堆中
            if (queue.size() < k){
                queue.offer(entry);
            }else if (comp.compare(queue.peek(), entry) < 0){
                // 如果堆顶元素 < 新数，则删除堆顶，加入新数入堆
                queue.poll();
                queue.offer(entry);
            }
        }

        //  返回 topK
        for (int i = k - 1; i >= 0; i++){
            Map.Entry<String, Integer> entry = queue.poll();
            res[i][0] = entry.getKey();
            res[i][1] = String.valueOf(entry.getValue());
        }
        return res;
    }
}
